#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>

using namespace std;

const int modes = 10009;

int answer[100];
int cnt[100];
int n, m, t;
string st;
string a[100];

void compute(int k)
{
	int temp = 1;
	for (int i = 0; i < st.size(); ++i)
	{
		if (st[i] == '+')
		{
			answer[k] += temp;
			temp = 1;
		}
		else
			temp = temp * cnt[st[i] - 'a'] % modes;
	}
}

void dfs(int k, int r)
{
	if (r < t) compute(t - r);
	if (k == m) return;
	dfs(k + 1, r);
	for (int i = 0; i < a[k].size(); ++i) ++cnt[a[k][i] - 'a'];
	dfs(k + 1, r - 1);
	for (int i = 0; i < a[k].size(); ++i) --cnt[a[k][i] - 'a'];
}

int	main()
{
	int task;
	cin >> task;
	for (int now_case = 0; now_case < task; ++now_case)
	{
		cin >> st >> t;
		cin >> m;
		for (int i = 0; i < m; ++i) cin >> a[i];
		memset(cnt, 0, sizeof(cnt));
		memset(answer, 0, sizeof(answer));
		dfs(0, t);
		for (int k = 1; k <= t; ++k)
			for (int i = 0; i < k; ++i) answer[k] = answer[k] * (i + 1) % modes;
		printf("Case #%d:", now_case + 1);
		for (int k = 1; k <= t; ++k) printf(" %d", answer[k]);
		puts("");
	}
	return 0;
}
